package cxydmmszl.chapter02.t020;

import java.util.HashMap;

/**
 * <li style="color: red;">Prob</li>
 * 复制含有随机指针节点的链表
 * <li style="color: red;">Desc</li>
 * 深拷贝一份节点还有随机指针的链表（链表结构不变）。
 * <li style="color: red;">Link</li>
 *
 * @author habitplus
 * @since 2021-08-29 13:56
 */
public class Solution {
    public static class RandNode {
        int val;
        RandNode rand;
        RandNode next;

        public RandNode(int val) {
            this.val = val;
        }

        public RandNode(int val, RandNode next, RandNode rand) {
            this.val = val;
            this.rand = rand;
            this.next = next;
        }
    }

    /**
     * 使用哈希表实现
     */
    public RandNode deepCopyLinkedListWithRandom(RandNode head) {
        if (head == null) return null;

        RandNode aux = head;
        HashMap<RandNode, RandNode> map = new HashMap<>();
        while (aux != null) {
            map.put(aux, new RandNode(aux.val));
            aux = aux.next;
        }

        aux = head;
        while (aux != null) {
            map.get(aux).next = map.get(aux.next);
            map.get(aux).rand = map.get(aux.rand);
            aux = aux.next;
        }

        return map.get(head);
    }

    /**
     * 仅使用额外的常量空间实现(奇偶链表）
     */
    public RandNode deepCopyLinkedListWithRandom02(RandNode head) {
        if (head == null) return null;
        // 隔空插入新节点

        RandNode aux = head, newNode, next;

        while (aux != null) {
            newNode = new RandNode(aux.val);
            newNode.next = aux.next;
            aux.next = newNode;
            aux = newNode.next;
        }

        // 更新 新节点的 rand 指针
        aux = head;
        while (aux != null) {
            newNode = aux.next;
            newNode.rand = aux.rand != null ? aux.rand.next : null;
            aux = aux.next.next;

        }

        // 拆分：更新 新节点的 next 指针
        RandNode newHead = head.next;
        aux = head;
        while (aux != null) {
            newNode = aux.next;
            next = aux.next.next;
            aux.next = next;
            newNode.next = next != null ? next.next : null;
            aux = next;
        }

        return newHead;
    }
}
